The present invention relates to a method of optimizing placement of elements in designing a semiconductor device.
As a method for combinational optimization, simulated annealing (SA) has been proposed (S. Kirkpatrick et al., xe2x80x9cOptimization by Simulated Annealingxe2x80x9d, SCIENCE, Vol. 220, No. 4598, pp.671-680, May 1983). SA is a method of accomplishing combinational optimization by using the Monte-Carlo (MC) method, which is a method for a computer simulation in the field of thermodynamics. In the case of using an SA process to solve an element placement problem, the element placement problem is regarded as a physical problem and a cost function for evaluating element placement is regarded as an energy function. Then, an estimated temperature is determined and a physical structure (placement structure) of a state of thermal equilibrium at the temperature is evaluated by the MC method based on the energy function (cost function). An arrangement of elements having a low cost function is determined approximately on the analogy of a physical state which approaches a minimum energy state as the temperature is gradually decreased.
Although it has been proved that SA provides a good approximate solution, the problem is encountered that enormous processing time is required for the solution to converge because it is necessary to gradually reduce the estimated temperature from an extremely high level to a low level.
To solve the problem, a simulated phase transition (SPT) method in which an optimum estimated temperature is determined previously to the execution of the MC method has been proposed (M. Toyonaga et al., xe2x80x9cPlacement Optimization by Simulated Phase Transitionxe2x80x9d, Technical Report of IEICE, CAS98-20, VLD98-20, DSP98-49, pp. 37-44, June 1998). In accordance with the SPT method, a temperature which improves the value of a cost function (cost value) most efficiently, i.e., an optimum estimated temperature Tc is determined first. By executing the MC method at the temperature Tc, the gradual cooling process from the extremely high temperature to the temperature Tc, which has been necessary in the case of implementing SA, becomes no more necessary.
In accordance with the SPT method described above, only one optimum estimated temperature Tc is obtained from one cost function. In addition, the temperature Tc is lower than the temperature at which the MC method in SA is initiated but higher than the temperature at which the approximate solution is obtained by it. In the SPT method, therefore, a new optimum estimated temperature Tcxe2x80x2 ( less than Tc) is determine sequentially by repeatedly performing the fixation of part of element placement in a range of estimated temperatures not more than Tc. However, there are cases where the approximate solution obtained may be inferior to that obtained by SA if the standard for the fixation of element placement has randomness and the setting of the standard is inappropriate.
It is therefore an object of the present invention to allow easy determination of a temperature effectiv in executing the MC method in a range of temperatures lower than an optimum estimated temperature derived from a cost function and ensure the achievement of improved element placement.
To attain the object, the present invention extracts at least one combination function from one cost function and determines an optimum estimated temperature derived from the combination function, thereby allowing easy determination of the temperature effective in executing the MC method in a range of temperatures lower than the optimum estimated temperature Tc derived from the original cost function.
Specifically, a method of optimizing placement of elements in accordance with the present invention is a method of optimizing placement of elements in designing a semiconductor device by using a cost function for evaluating the placement of elements, the cost function being expressed as a sum of p (p is an integer not less than 2) partial functions and varying with an estimated temperature as a parameter, the method comprising: a first step of inputting a net list and a cell library and effecting an initial arrangement of elements to be arranged; a second step of extracting functions each expressed with either one of the p partial functions of the cost function or, when p is an integer not less than 3, expressed as a sum of a combination of not less than 2 and not more than (pxe2x88x921) partial functions of the p partial functions of the cost function as q (q is an integer not less than 1 and not more than (2pxe2x88x922)) combination functions; a third step of randomly selecting two elements adjacent to each other from the elements to be arranged, calculating one optimum estimated temperature based on a difference between values of the cost function before and after the two elements are interchanged in position, and calculating q optimum estimated temperatures based on differences between respective values of the q combination functions before and after the interchange; a fourth step of recording, in a temperature schedule list, the temperatures of the q optimum estimated temperatures derived from the q combination functions which are lower than the optimum estimated temperature derived from the cost function together with the optimum estimated temperature derived from the cost function; and a fifth step of executing a Monte-Carlo method based on a random positional interchange between the elements to be arranged using the cost function in order of the decreasing temperatures recorded in the schedule list and thereby improving the initial arrangement.
The second step may include a step of extracting all or part of the p functions expressed with the respective p partial functions of the cost function as all or part of the q combination functions. When p is an integer not less tan 3, the second step may include a step of extracting all or part of (2pxe2x88x92pxe2x88x922) functions each expressed as a sum of a combination of not less than 2 and not more than (pxe2x88x921) partial functions of the p partial functions of the cost function as all or part of the q combination functions.
Preferably, the fourth step includes a step of updating the temperature schedule such that a plurality of temperatures having a difference not exceeding a given threshold value therebetween are represented by one of the temperatures.